//https://leetcode.cn/problems/intersection-of-two-linked-lists-lcci/
package codeRandomThoughts.InterviewTest0207链表相交;

import codeRandomThoughts.utils.ListNode;

public class Solution {
    /**
     * 这个解法多少有点太暴力了,得想个更好的
     *
     * @param headA
     * @param headB
     * @return
     */
    public ListNode getIntersectionNode1(ListNode headA, ListNode headB) {
        //还是得用伪节点
        ListNode dummyHeadA = new ListNode();
        ListNode dummyHeadB = new ListNode();
        dummyHeadA.next = headA;
        dummyHeadB.next = headB;
        ListNode currA = dummyHeadA;
        ListNode currB = dummyHeadB;
        if (headA == null || headB == null) {
            return null;
        }
        if (headA == headB) {
            return headB;
        }
        while (currA.next != null) {
            while (currB.next != null) {
                if (currA.next == currB.next) {
                    return currA.next;
                }
                currB = currB.next;
            }
            currB = dummyHeadB;
            currA = currA.next;
        }
        return null;
    }

    /**
     * 以后遇见链表的题目,先构造假头节点,没坏处就是了
     *
     * @param headA
     * @param headB
     * @return
     */
    public ListNode getIntersectionNode2(ListNode headA, ListNode headB) {
        //还是得用伪节点
        ListNode dummyHeadA = new ListNode();
        ListNode dummyHeadB = new ListNode();
        dummyHeadA.next = headA;
        dummyHeadB.next = headB;
        ListNode currA = dummyHeadA;
        ListNode currB = dummyHeadB;
        if (headA == null || headB == null) {
            return null;
        }
        if (headA == headB) {
            return headB;
        }
        //上面的都是前置工作
        //把currA和currB置于同一起点
        int lengthA = 0;
        int lengthB = 0;
        while (currA.next != null) {
            currA = currA.next;
            lengthA++;
        }
        while (currB.next != null) {
            currB = currB.next;
            lengthB++;
        }
        currA = dummyHeadA;
        currB = dummyHeadB;
        int diff = lengthA - lengthB;
        if (diff > 0) {
            for (int i = 0; i < diff; i++) {
                currA = currA.next;
            }
        } else {
            diff = -diff;
            for (int i = 0; i < diff; i++) {
                currB = currB.next;
            }
        }
        //A和B一起前进 相交就停止
        while (currA != currB) {
            currA = currA.next;
            currB = currB.next;
        }
        return currA;
    }
}
